We prove the approximation ratio 8/5 for the metric $\{s,t\}$-path-TSPproblem, and more generally for shortest connected $T$-joins. The algorithm that achieves this ratio is the simple "Best of Many" versionof Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys(2012), which consists in determining the best Christofides $\{s,t\}$-tour outof those constructed from a family $\Fscr_{>0}$ of trees having a convexcombination dominated by an optimal solution $x^*$ of the fractionalrelaxation. They give the approximation guarantee $\frac{\sqrt{5}+1}{2}$ forsuch an $\{s,t\}$-tour, which is the first improvement after the 5/3 guaranteeof Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao(2012) extended this result to a 13/8-approximation of shortest connected$T$-joins, for $|T|\ge 4$. The ratio 8/5 is proved by simplifying and improving the approach of An,Kleinberg and Shmoys that consists in completing $x^*/2$ in order to dominatethe cost of "parity correction" for spanning trees. We partition the edge-setof each spanning tree in $\Fscr_{>0}$ into an $\{s,t\}$-path (or moregenerally, into a $T$-join) and its complement, which induces a decompositionof $x^*$. This decomposition can be refined and then efficiently used tocomplete $x^*/2$ without using linear programming or particular properties of$T$, but by adding to each cut deficient for $x^*/2$ an individually tailoredexplicitly given vector, inherent in $x^*$. A simple example shows that the Best of Many Christofides algorithm may notfind a shorter $\{s,t\}$-tour than 3/2 times the incidentally common optima ofthe problem and of its fractional relaxation.
展开▼
机译：对于公制$ \ {s，t \} $-path-TSP问题，我们证明了近似比率8/5，对于更短的连接$ T $ -joins，我们证明了近似比率。实现此比率的算法是简单的Christofides算法（1976年）的“最佳多数”版本，由An，Kleinberg和Shmoys（2012年）建议，其中包括确定最佳Christofides $ \ {s，t \} $-从由家庭$ \ Fscr _ {> 0} $的树木组成的树中巡回，这些树木的凸组合由分数松弛的最优解$ x ^ * $支配。他们为这样的$ \ {s，t \} $行程提供近似保证$ \ frac {\ sqrt {5} +1} {2} $，这是继Hoogeveen的Christofides类型算法的5/3保证之后的第一个改进。 （1991）。 Cheriyan，Friggstad和Gao（2012）将此结果扩展为最短连通$ T $ -joins的13/8逼近，为$ | T | \ ge 4 $。通过简化和改进An，Kleinberg和Shmoys的方法证明了比率8/5，该方法包括完成$ x ^ * / 2 $，以便支配跨树的“奇偶校正”的成本。我们将$ \ Fscr _ {> 0} $中每个生成树的边集划分为$ \ {s，t \} $路径（或更一般地说，为$ T $ -join）及其补码，从而产生一个$ x ^ * $的分解。可以精简此分解，然后有效地用于完成$ x ^ * / 2 $，而无需使用线性编程或$ T $的特定属性，但是通过向$ x ^ * / 2 $的每个有缺陷的割加一个单独定制的明确给出的矢量， $ x ^ * $中固有的。一个简单的例子表明，“最佳克里斯托弗蒂斯算法”可能找不到比问题及其分数松弛的偶然常见最优方法短3/2倍的$ \ {s，t \} $行程。
展开▼
